#include "avlTree1.h"
#include <stdlib.h>
#include "../logger/logger.h"
#define Max(a, b) (a > b ? a : b)

AvlTree MakeEmpty(AvlTree T)
{
    if (T)
    {
        MakeEmpty(T->Left);
        MakeEmpty(T->Right);
        free(T);
    }

    return NULL;
}
Position Find(ElementType x, AvlTree T)
{
    if (!T)
        return T;
    if (x < T->Element)
        return Find(x, T->Left);
    else if (x > T->Element)
        return Find(x, T->Right);
    else
        return T;
}
Position FindMin(AvlTree T)
{
    if (!T)
        return T;
    if (T->Left)
        return FindMin(T->Left);
    else
        return T;
}
Position FindMax(AvlTree T)
{
    if (!T)
        return T;
    if (T->Right)
        return FindMax(T->Right);
    else
        return T;
}

int Height(AvlTree T)
{
    if (!T)
        return -1;
    return T->Height;
}

static AvlTree SingleRotateWithLeft(AvlTree T)
{
    Position Tmp;
    Tmp = T->Left;
    T->Left = Tmp->Right;
    Tmp->Right = T;
    Tmp->Height = Max(Height(Tmp->Right), Height(Tmp->Left)) + 1;
    T->Height = Max(Height(T->Right), Height(T->Left)) + 1;
    return Tmp;
}

static AvlTree SingleRotateWithRight(AvlTree T)
{
    Position Tmp;
    Tmp = T->Right;
    T->Right = Tmp->Left;
    Tmp->Left = T;
    Tmp->Height = Max(Height(Tmp->Right), Height(Tmp->Left)) + 1;
    T->Height = Max(Height(T->Right), Height(T->Left)) + 1;
    return Tmp;
}

//出现左右的情况，先右旋转再左旋转
static AvlTree DoubleRotateLeftRight(AvlTree T)
{
    T->Left = SingleRotateWithRight(T->Left);
    return SingleRotateWithLeft(T);
}

//出现右左的情况，先左旋转再右旋转
static AvlTree DoubleRotateRightLeft(AvlTree T)
{
    T->Right = SingleRotateWithLeft(T->Right);
    return SingleRotateWithRight(T);
}

AvlTree Insert(ElementType x, AvlTree T)
{
    if (!T)
    {
        T = malloc(sizeof(*T));
        if (!T)
            FatalError("OUt of space!");
        T->Element = x;
        T->Height = 0;
        T->Left = NULL;
        T->Right = NULL;
    }
    else if (x < T->Element)
    {
        T->Left = Insert(x, T->Left);
        if (Height(T->Left) - Height(T->Right) == 2)
            if (x < T->Left->Element)
                //left left
                T = SingleRotateWithLeft(T);
            else
                T = DoubleRotateLeftRight(T);
    }
    else if (x > T->Element)
    {
        T->Right = Insert(x, T->Right);
        if (Height(T->Right) - Height(T->Left) == 2)
            if (x > T->Right->Element)
                //Right Right
                T = SingleRotateWithRight(T);
            else
                T = DoubleRotateRightLeft(T);
    }
    //Height会递归增长
    T->Height = Max(Height(T->Left), Height(T->Right)) + 1;
    return T;
}

//lazy delete
AvlTree Delete(ElementType X, AvlTree T)
{
    if (!T)
        return NULL;
    if (X < T->Element)
        T->Left = Delete(X, T->Left);
    else if (X > T->Element)
        T->Right = Delete(X, T->Right);
    else
        T->Deleted = 1;
    return T;
}
ElementType Retrieve(Position P);

static void Print(AvlTree T, int Depth, int Right)
{
    if (!T)
        return;

    for (int i = 0; i < Depth; i++)
        printf(" ");
    printf("%d:%s", T->Element, Right ? "右" : "左");
    if (T->Deleted)
        printf("-del");
    printf("\n");

    Print(T->Left, Depth + 1, 0);
    Print(T->Right, Depth + 1, 1);
}

void PrintTree(AvlTree T)
{
    Print(T, 0, 0);
}